package com.wx.leetcode;

import java.util.Arrays;

/**
 * @desc: 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * @author: wx
 * @time: 2020/6/15 6:10 PM
 */
public class SolutionTopic {


    public static void main(String args[]) {
        System.out.println(threeSumClosest(new int[]{-1, 2, 1, -4}, 1));

    }

    /**
     * 思路：三数之和，来判断接近目标数字
     */                
    public static int threeSumClosest(int[] nums, int target) {
        //排序
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int start = i + 1;
            int end = nums.length - 1;

            while (start < end) {
                int sum = nums[start] + nums[end] + nums[i];

                //目标-总数取绝对值=差值
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }
                //如果> 缩小范围
                else if (sum > target) {
                    end--;

                }
                //如果< 加大范围
                else  if (sum < target){
                    start++;

                }
                //如果= 直接返回
                else {
                    return ans;
                }
            }


        }

        return ans;
    }


}
